package com.ycl.javacore.algorithm;

import org.junit.Test;

import java.util.HashMap;

/**
 * User: OF1089 杨成龙
 * Date: 2019/7/16
 * Time: 10:44 AM
 * Desc: 类描述
 * <p>
 * 这个题目说的是，给你一个整数数组和一个目标值，你要找到数组里两个整数， 它们的和等于目标值。然后返回这两个整数的下标。
 * <p>
 * 比如说给你的整数数组是：
 * <p>
 * 1, 2, 3, 6, 8, 11
 * <p>
 * 目标值是 10。那么，满足条件的两个整数是，2 和 8，它们的和是 10。所以你要返回它们的下标是 1 和 4。
 */
public class AlgoCasts02 {


    /**
     * @param nums
     * @param target
     * @return
     * 通过hashmap的方式，时间复杂度O(n)  空间复杂度O(n)
     */
    private int[] getTwoNumSumToGivenValueHashMap(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int numNeeds = target - nums[i];
            if (map.containsKey(numNeeds)) {
                return new int[]{map.get(numNeeds), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    /**
     * @param nums
     * @param target
     * @return
     * 遍历两层数组，时间复杂度O(n^2)  空间复杂度O(1)
     */
    private int[] getTwoNumSumToGivenValueBruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    @Test
    public void testClient() {
        int[] nums = new int[]{1, 2, 4, 6, 8};
        int target = 10;
        int[] result = getTwoNumSumToGivenValueHashMap(nums, target);
//        int[] result = getTwoNumSumToGivenValueBruteForce(nums,target);
        System.out.println(result);
    }

    public static int[][] getTwoNumSum2Given(int[] nums,int target) {
        int[][] targetResult = new int[][]{};
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    targetResult[i] = new int[]{i,j};
                }
            }
        }
        return targetResult;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 4, 6, 8};
        int[][] target = (int[][]) getTwoNumSum2Given(nums,6);
    }

}
